1. Field of the Invention
The present invention is directed to communication protocols and, more particularly, to an apparatus and method for enabling pipelined, sliding-window flow control for end-to-end communication sessions over a half duplex communication channel.
2. Description of the Invention Background
Most computer networks are organized as a series of layers, with each layer being supported by the preceding layer. Dividing network functions among various layers simplifies the functions which each layer must perform. Each layer provides services to the layer directly above it, which services are provided in a transparent manner such that the layer receiving the services is not aware, and does not: care, how the services are actually implemented. In that manner, a very complex network can be constructed of moderately complex, or even simple, layers.
Each layer communicates with the layer directly below it through an interface and communicates with the same layer on another machine through a protocol. No data is directly transferred from a layer on one machine to a layer on another machine, except at the lowest layer. At the lowest layer, there is physical communication between the machines. At levels above the lower level, communication between levels on different machines is virtual. The set of layers: and protocols is called the network architecture. The details of the implementation and the specification of the interfaces are not part of the architecture. Thus, it is not necessary that the interfaces on all machines be the same. It is, however, necessary that each machine correctly use all the protocols, otherwise the various layers of the network architecture will not be able to properly communicate.
Certain networks have become well known such as the Defense Advanced Research Projects Agency at the U.S. Department of Defense (ARPANET), IBM's Systems Network Architecture (SNA), and Digital Equipment Corporation's DEC-NET. The use of different system architectures raises the problem of communication between networks. As a first step toward international standardization of protocols, the International Standards Organization (ISO) has proposed a reference model of Open Systems Interconnection (OSI) which has seven layers. A model shown in FIG. 1 is closely based on the ISO OSI reference model. The lowest layer, called the physical layer, is concerned with transmitting raw bits over a communication channel. At the data link layer, the preparation of frames for transmission by the physical layer, or the organization into frames of data received from the physical layer, is carried out. The network layer, which is sometimes referred to as the communication subnet layer, controls the operation of the subnet. The network layer's primary function is to determine how packets of information are routed within the subnet. The transport layer's purpose is to accept a message from the layer immediately above it, i.e. the session layer, and divide the message up into packets to be handed to the network layer.
There is a difference between the transport layer, and all layers above it, from the physical, data link, and network layers. The transport layer, and all higher layers, are end-to-end layers in that a program on a source machine carries on a session with a similar program on a destination machine, using the appropriate control messages. At the network layer, and the lower layers, protocols are carried out by each machine and its immediate neighbors, which may or may not be the ultimate source and ultimate destination machines, i.e. the ultimate source and ultimate destination machines may be separated by many logical units. Thus, it is said that the physical, data link, and network layers are chained while the transport layer, and layers above it, are end-to-end.
The session layer acts primarily as the user's interface into the network. The session layer is responsible for establishing a connection with the destination machine. Once a connection is established, the session layer manages the dialogue between the source and destination machines.
The presentation layer is a layer which is provided to carry out frequently requested functions that merit having a general solution rather than complicating the topmost, or application layer. For example, the presentation layer may be used for text compression, encryption, or other similar functions which are of general interest and whose implementation is called upon sufficiently frequently to merit having the presentation layer perform that function.
The application layer is the layer at which applications are run. The content of the application layer is therefore up to the particular user.
There are several design issues that are present in most or all of the layers. For example, each layer must have a mechanism for establishing and terminating connections with other layers. Because a network normally has many different types of logical units connected to it, addressing the desired logical unit, establishing a connection, and terminating the connection when communication is completed, raises a number of problems. Additionally, at the data level, data may travel in one direction (simplex communication), travel in either direction (half-duplex communication), or travel in both directions simultaneously (full duplex communication). The protocol must also determine how many logical channels the connection corresponds to, and the priorities of those channels. Error detection and error correcting codes must also be implemented. Even when the foregoing issues have been addressed, a serious problem arises at every level with respect to how to keep a fast transmitting machine from swamping a slow receiving machine with data. A simple solution is to send a single frame, and await acknowledgement that the frame has been correctly received before sending the next frame. However, the time required for both the original message frame and the acknowledgement signal to be received can have a substantial impact on transmission efficiency. For example, consider a 50 kbps channel with a 500 millisecond round trip propagation delay. Consider the transmission of several 1,000-bit frames. At time t=0, the transmitting unit starts sending the first frame. At time t=20 milliseconds, the first frame has been completely sent. Not until time t=270 milliseconds has the frame fully arrived at the receiving unit, and not until time t=520 milliseconds has the acknowledgement signal sent by the receiving unit been received by the transmitting unit. That means that the transmitter was idle during 500 milliseconds of the 520 millisecond time period, or 96% of the time. Thus, only 4% of the available bandwidth was used.
If the requirement that the transmitting unit suspend transmissions until receiving an acknowledgement from the receiving unit can be circumvented, then a much more efficient use of the available band width can be obtained. One possible solution is to allow the transmitting unit to transmit up to W frames before waiting for an acknowledgement, instead of just one frame. With an appropriate choice of W, the transmitting unit will be able to continuously transmit frames for a time equal to the round-trip transit time without overloading the buffers of the receiving unit. In the above example, W should be at least 26. The transmitting unit begins sending at time t=0 as before. By the time it has finished sending 26 frames, at time t=520, the acknowledgement for the first frame will have just arrived. Thereafter, acknowledgements will arrive spaced by 20 milliseconds so the transmitter always gets permission to continue transmitting just when such permission is needed. At all times, no more than 26 unacknowledged frames are outstanding. That may be referred to as a window size of 26. Filling the communications channel with frames, and receiving an acknowledgement just in time for transmission of the next frame, is referred to as pipelining. As is apparent, pipelining provides a substantially more efficient use of available bandwidth than "stop-and-wait" communication schemes.
Pipelining can be implemented at various layers within the network provided that the communication protocols of that layer are designed to support pipelining. Unfortunately, there are numerous concerns at each layer directed to that layer's primary function, such that protocols are not always capable of supporting pipelining.
For example, consider IBM's SNA network, operating an LU6.2 protocol over a half-duplex communication channel. In that environment, at the application layer, there is no defined function to acknowledge the receipt of data other than having the transmitting application wait for acknowledgement prior to sending the next buffer of data. To address that particular problem, application programmers use one of two techniques. The transmitting unit may send data with a request indicator and then wait for a reply to insure that the request was processed successfully. To improve throughput, the request indicator may be sent only every N frames. Alternatively, the transmitting unit may send a confirmation request which implicitly waits for an acknowledgement from the receiving unit. To improve throughput, that may be done after N frames have been transmitted.
Those two approaches are functionally equivalent but implemented using different communication functions. The sending application for the confirmation request may be written as follows:
______________________________________ loop: Read Data from file. (MC.sub.--)Send.sub.-- Data over communication network. Increment i If i&gt;N (MC.sub.--)Confirm /* Send a Confirm Request and wait for Reply Set i = 0 endif goto loop: ______________________________________
The corresponding receiving application segment is:
______________________________________ loop: (MC.sub.--)Receive.sub.-- And.sub.-- Wait from communication network. If What.sub.-- Received indicator is CONFIRM (MC.sub.--)Confirmed Reply over communication network. else Write Data to File. endif goto loop: ______________________________________
As is seen, the confirmation request algorithm is equivalent to the stop-and-wait techniques described above, except that the stop-and-wait occurs after N frames have been sent rather than after every frame.
The limitation of the conversational request and confirmation request is that when the Confirm function is called, the transmitting application stops and waits for the Confirmed Reply to be returned. If it takes 500 milliseconds for the receiving unit to receive the Confirm Request, and another 500 milliseconds for the transmitting unit to receive the Confirmed Reply, the transmitting application will wait 1,000 milliseconds. If the receiving unit is faster than the transmitting unit, that time is wasted. Thus, the need exists for implementing pipelined type communications at the application layer in a system architecture and protocol not designed to support such communications at that layer.